// Written by Craig'n'Dave
using System;
// Binary tree using an array
namespace ConsoleApp1
{
    class Program
    {
        public class Binary_tree
        {
            private static int depth = 5;
            private static int max = 2 ^ (depth + 1) - 1;
            private static string[] btree = new string[max];
            public int root = 0;

            public bool add(string item)
            {
                int current_node = root;
                // Find current position
                while ((current_node < max) && (btree[current_node] != null))
                {
                    // Using ordinal string comparison, returns < 0, 0 or > 0
                    if (String.Compare(item, btree[current_node]) < 0)
                    {
                        current_node = (2 * current_node) + 1;
                    }
                    else
                    {
                        current_node = (2 * current_node) + 2;
                    }
                }
                // Check overflow
                if (current_node < max)
                {
                    btree[current_node] = item;
                    return true;
                }
                else
                {
                    return false;
                }
            }

            public bool delete(string item)
            {
                // Using Hibbard's algorithm (leftmost node of right sub-tree is the successor)
                // Find the node To delete
                int current_node = root;
                while ((current_node < max) && (btree[current_node] != item))
                {
                    if (String.Compare(item, btree[current_node]) < 0)
                    {
                        current_node = (2 * current_node) + 1;
                    }
                    else
                    {
                        current_node = (2 * current_node) + 2;
                    }
                }

                if ((current_node < max) && (btree[current_node] == item))
                {
                    // Handle 3 cases depending on the number Of child nodes
                    int left_node = (2 * current_node) + 1;
                    int right_node = (2 * current_node) + 2;
                    if ((left_node < max) && (btree[left_node] == null) && (right_node < max) && (btree[right_node] == null))
                    {
                        // Node has no children
                        btree[current_node] = null;
                    }
                    else if ((left_node < max) && (btree[left_node] != null) && (right_node < max) && btree[right_node] != null)
                    {
                        // Node has two children
                        // Find the smallest value In the right Sub-tree (successor node)
                        int smallest = right_node;
                        while (((2 * smallest) + 1 < max) && (btree[2 * smallest] + 1 != null))
                        {
                            smallest = (2 * smallest) + 1;
                        }
                        btree[current_node] = btree[smallest];
                        btree[smallest] = null;
                    }
                    else if ((left_node < max) && (btree[left_node] != null))
                    {
                        // Node has one left child
                        btree[current_node] = btree[left_node];
                        btree[left_node] = null;
                    }
                    else if ((right_node < max) && (btree[right_node] != null))
                    {
                        // Node has one right child
                        btree[current_node] = btree[right_node];
                        btree[right_node] = null;
                    }
                    return true;
                }
                else
                {
                    return false;
                }
            }

            public void preorder(int current_node)
            {
                // Visit each node: NLR
                if ((current_node < max) && (btree[current_node] != null))
                {
                    Console.WriteLine(btree[current_node]);
                    preorder((2 * current_node) + 1);
                    preorder((2 * current_node) + 2);
                }
            }
            public void inorder(int current_node)
            {
                // Visit each node: LNR
                if ((current_node < max) && (btree[current_node] != null))
                {
                    inorder((2 * current_node) + 1);
                    Console.WriteLine(btree[current_node]);
                    inorder((2 * current_node) + 2);
                }
            }
            public void postorder(int current_node)
            {
                // Visit each node: LNR
                if ((current_node < max) && (btree[current_node] != null))
                {
                    postorder((2 * current_node) + 1);
                    postorder((2 * current_node) + 2);
                    Console.WriteLine(btree[current_node]);
                }
            }
            public void bft()
            {
                // Visit each node: BFT
                for (int current_node = 0; current_node < max; current_node++)
                {
                    if (btree[current_node] != null)
                    {
                        Console.WriteLine(btree[current_node]);
                    }
                }
            }

        }


        // Main program starts here
        static void Main(string[] args)
        {
            string[] items = { "E", "B", "G", "A", "C", "F", "H" };
            Binary_tree binary_tree = new Binary_tree();
            for (int index = 0; index < items.Length; index++)
            {
                binary_tree.add(items[index]);
            }
            // Traverse the binary tree
            Console.WriteLine("Breadth first traversal:");
            binary_tree.bft();
            Console.WriteLine("Pre-order traversal:");
            binary_tree.preorder(binary_tree.root);
            Console.WriteLine("In-order traversal:");
            binary_tree.inorder(binary_tree.root);
            Console.WriteLine("Post-order traversal:");
            binary_tree.postorder(binary_tree.root);
        }
    }
}
